#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys,string
from ClusterUtility import GetEuclidDistance, ShowClusterResult, GetClusterCenter

_DEBUG = False 

"""
@desc 获取两个聚类之间的距离
@c1,c2 两个类
@return 两个类之间的距离
Note: 两个聚类之间的距离的计算方式有多种，在这里采用“类中心间距法”
"""
def GetClusterDistance(cluster1, cluster2):
    #分别计算c1和c2的中心点
    center1 = GetClusterCenter(cluster1)
    center2 = GetClusterCenter(cluster2)
    return GetEuclidDistance(center1, center2)

"""
@desc 采用层次聚类法（系统聚类法，又称最小距离聚类法，笔者觉得层次聚类法更贴切）
@count 最终得到的类的个数
@DataSet 数据集
@return 聚类结果
"""
def LevelCluster(count, DataSet):
    ClusterSet = []
    #初始化所有的类，即将所有单个的向量都作为一类
    for v in DataSet:
        cluster = []
        cluster.append(v)
        ClusterSet.append(cluster)
    #ShowClusterResult(ClusterSet)
    #print("-----------")
    #构造距离数组，在这里采用list的嵌套
    dist = []
    flag = False
    for i in range(len(ClusterSet)):
        array = []
        for j in range(len(ClusterSet)):
            if j<i:
                tmp = GetClusterDistance(ClusterSet[i], ClusterSet[j])
                array.append(tmp)
            elif j==i:
                array.append(0)
            #不考虑 i != j 的情况
            if j < i:
                if not flag:
                    mindist = tmp
                    vi = i; vj = j;
                    flag = True
                else:
                    if tmp < mindist:
                        mindist = tmp
                        vi = i; vj = j;
        dist.append(array)
    
    k = len(DataSet) #k记录现有的分类数
    while k > count:
        #将vi类合并到vj类中，并修改各个距离
        #Note: vi >= vj
        ClusterSet[vj] = ClusterSet[vi] + ClusterSet[vj]
        #ClusterSet[vj] = list(set(ClusterSet[vj])) #删除重复元素
        
        #重新计算类vj与其他类之间的距离 dist
        #修改第vj类相对与类i的距离(vj>i)
        dist[vj] = []
        for i in range(k):
            if i<vj:
                tmp = GetClusterDistance(ClusterSet[i], ClusterSet[vj])
                dist[vj].append(tmp)
        #修改(i, vj)类型的距离，其中 i>vj
        for i in range(vi+1, k):
            dist[i][vj] = GetClusterDistance(ClusterSet[i], ClusterSet[vj])
            del dist[i][vi]
        del ClusterSet[vi]
        del dist[vi]
        k = k - 1
        #找出两个间距最小的聚类
        flag = False
        for i in range(1, len(dist)):
            for j in range(0, i-1):
                if not flag:
                    mindist = dist[i][j]
                    vi=i; vj=j
                else:
                    if mindist > dist[i][j]:
                        mindist = dist[i][j]
                        vi=i; vj=j

    ShowClusterResult(ClusterSet)
    
def test(argv):
    #在这里构造DataSet
    DataSet = []
    DataSet.append((0, 1, 3, 1, 3, 4))
    DataSet.append((3, 3, 3, 1, 2, 1))
    DataSet.append((1, 0, 0, 0, 1, 1))
    DataSet.append((2, 1, 0, 2, 2, 1))
    DataSet.append((0, 0, 1, 0, 1, 0))
    if len(argv) != 2:
        print("Usage: python LevelCluster.py <ClusterCount>")
        return 
    else:
        count = string.atoi(argv[1])
        #print()
        assert count <= len(DataSet) and count>1
        LevelCluster(count, DataSet)
    return
if __name__ == "__main__":
    if _DEBUG == True: 
        import pdb 
        pdb.set_trace()     
    test(sys.argv)
